class Solution {
public:
    int specialPerm(vector<int>& nums) {
        int n = nums.size(), u = (1 << n) - 1;
        vector<vector<long long>> f(u, vector<long long>(n));
        ranges::fill(f[0], 1LL);
        for (int s = 1; s < u; s++) {
            for (int i = 0; i < n; i++) {
                if (s >> i & 1) {
                    continue;
                }
                for (int j = 0; j < n; j++) {
                    if ((s >> j & 1) && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) {
                        f[s][i] += f[s ^ (1 << j)][j];
                    }
                }
            }
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += f[u ^ (1 << i)][i];
        }
        return ans % 1'000'000'007;
    }
};